Let 𝚷\mathbf{\Pi} be a properly scaled JL matrix (random Gaussian, sparse random etc.) with m=O(dĪĩ2)m=O(\frac{d}{\epsilon^2}) rows[1]. Then with probability 9/109/10, for any 𝐀∈ℝn×d\mathbf{A} \in \mathbb{R}^{n \times d} and 𝐛∈ℝn\mathbf{b} \in \mathbb{R}^n,

‖𝐀𝐱~−𝐛‖22≤(1+Īĩ)‖𝐀𝐱∗−𝐛‖22\lVert \mathbf{A}\tilde{\mathbf{x}}-\mathbf{b}\rVert_2^2 \leq (1+\epsilon)\lVert \mathbf{A}\mathbf{x}^*-\mathbf{b}\rVert_2^2

where 𝐱~=arg⁡min𝐱⁡‖𝚷𝐀𝐱−𝚷𝐛‖22\tilde{\mathbf{x}} = \arg\min_\mathbf{x}\lVert \mathbf{\Pi Ax}-\mathbf{\Pi b}\rVert_2^2.

  1. this can be improved to O(d/Īĩ)O(d/\epsilon) with tighter analysis ↩ī¸Ž